class Solution {
//    在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。
//    请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
//    示例 1:
//    输入：record = [9, 7, 5, 4, 6]
//    输出：8
//    解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
    public int reversePairs(int[] record) {
        //归并排序
        return mergeSort(record, 0, record.length - 1);
    }
    private int mergeSort(int[] nums, int left, int right){
        if(left >= right) return 0;
        int mid = (left + right) / 2;
        int l = mergeSort(nums, left, mid);
        int r = mergeSort(nums, mid + 1, right);
        //合并
        int res = merge(nums, left, mid, right);
        return l + r + res;
    }
    private int merge(int[] nums, int left, int mid, int right){
        int s1 = left;
        int s2 = mid + 1;
        int cur = 0;
        int[] tmpArr = new int[right - left + 1];
        int res = 0;
        //合并两个有序数组 - 升序
        while(s1 <= mid && s2 <= right){
            if(nums[s1] > nums[s2]){
                tmpArr[cur++] = nums[s2++];
                res += (mid - s1 + 1);
            }else{
                tmpArr[cur++] = nums[s1++];
            }
        }
        while(s1 <= mid){
            tmpArr[cur++] = nums[s1++];
        }
        while(s2 <= right){
            tmpArr[cur++] = nums[s2++];
        }
        for(int i = left; i <= right; i++){
            nums[i] = tmpArr[i - left];
        }

        return res;
    }
}